#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <deque>
#include <forward_list>
#include <array>
#include <string>
#include <stdexcept>
#include <stack>

using namespace std;

void pr_9_1()
{
    list<deque<int>> list_dq;
}

bool pr_9_4(vector<int>::iterator b, vector<int>::iterator e, int val)
{
    while (b != e) {
        if (*b == val) {
            return true;
        } else {
            ++b;
        }
    }
    return false;
}

vector<int>::iterator
pr_9_5(vector<int>::iterator beg, vector<int>::iterator end, int val)
{
    for(; beg != end; ++beg) {
        if (*beg == val) {
            return beg;  // 搜索成功，返回元素对应的迭代器
        }
    }
    return end;  // 搜索失败，返回尾后迭代器
}

void pr_9_11()
{
    // 六种初始化 vector的方法
    vector<int> v1 = {0,1,2,3,4,5,6,7,8,9};  // 列表初始化
    vector<int> v2(v1);
    vector<int> v3 = v1;
    vector<int> v4(v1.begin(), v1.end());
    vector<int> v5{0,1,2,3,5,6,7,8,9};
    vector<int> v6(10, 1);  // 10个1
}

void pr_9_13()
{
    // 用 list<int> 初始化 vector<double>
    list<int> list1{1,3,5,7,9,11,13,15,17,19,21};
    vector<double> v1(list1.begin(), list1.end());
    for (const auto i : v1) {
        cout << i << " ";
    }
    cout << endl;
    // 用 vector<int> 初始化 vector<double>
    vector<int> v2(10, 112);
    vector<double> v3(v2.cbegin(), v2.cend());
    for (const auto i : v3) {
        cout << i << " ";
    }
    cout << endl;
}

void pr_9_14()
{
    list<const char *> clist = {"a", "an", "the"};
    vector<string> sVec;
    sVec.assign(clist.begin(), clist.end());
    for (const auto &s : sVec) {
        cout << s << " ";
    }
    cout << endl;
}

void pr_9_15(vector<int> &v1, vector<int> &v2)
{
    if (v1 == v2) {
        cout << "v1 == v2" << endl;
    } else {
        cout << "v1 != v2" << endl;
    }
}

void pr_9_16(list<int> &il, vector<int> &v1)
{
    vector<int> v;
    v.assign(il.cbegin(), il.cend());
    if (v == v1) {
        cout << "il == v1" << endl;
    } else if (v < v1) {
        cout << "il < v1" << endl;
    } else {
        cout << "il > v1" << endl;
    }
}

void pr_9_18()
{
    deque<string> dp;
    string word;
    while (cin >> word) {
        dp.push_back(word);
    }
    for (auto it = dp.cbegin(); it != dp.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

void pr_9_19()
{
    list<string> slist;
    string word;
    while (cin >> word) {
        slist.push_back(word);
    }
    for (auto it = slist.cbegin(); it != slist.cend(); ++it) {
        cout << *it << " ";
    }
    cout << endl;
}

void pr_9_20()
{
    int val;
    list<int> ilist;
    deque<int> dp1, dp2;
    while (cin >> val) {
        ilist.push_back(val);
    }
    for (auto it = ilist.cbegin(); it != ilist.cend(); ++it) {
        if (*it % 2 == 0) {
            dp1.push_back(*it);
        } else {
            dp2.push_back(*it);
        }
    }
    cout << endl;
    for (auto i : dp1) {
        cout << i << " ";
    }
    cout << endl;
    for (auto i : dp2) {
        cout << i << " ";
    }
    cout << endl;
}

void pr_9_22()
{
    vector<int> iv = {1, 1, 2, 1};  // int 的 vector
    int some_val = 1;
    vector<int>::iterator iter = iv.begin();
    int org_size = iv.size(), new_ele = 0;  // 原大小和新元素个数
    // 每个循环步骤都重新计算 mid，保证正确指向 iv 原中央元素
    while (iter != (iv.begin() + org_size / 2 + new_ele)) {
        if (*iter == some_val) {
            iter = iv.insert(iter, 2 * some_val);  // iter指向新元素
            new_ele++;
            iter++;
            iter++;  // 将 iter推进到旧元素的下一个位置
        } else {
            iter++;
        }
    }
    // 用 begin() 获取 vector首元素迭代器，遍历 vector中的所有元素
    for (iter = iv.begin(); iter != iv.end(); ++iter) {
        cout << *iter << endl;
    }
}

void pr_9_24()
{
    vector<int> vec;
    cout << vec.at(0) << endl;
    cout << vec[0] << endl;
    cout << vec.front() << endl;
    cout << vec.back() << endl;
}

void pr_9_25()
{
    list<int> lst = {0,1,2,3,4,5,6,7,8,9};
    auto elem1 = lst.begin();
    auto elem2 = lst.begin();
    lst.erase(elem1, elem2);
}

void pr_9_26()
{
    int ia[] = {0,1,1,2,3,5,8,13,21,55,89};
    vector<int> ivec;
    list<int> ilist;

    ivec.assign(begin(ia), end(ia));
    ilist.assign(begin(ia), end(ia));

    auto viter = ivec.begin();
    while (viter != ivec.end()) {
        if (!(*viter & 1)) {
            viter = ivec.erase(viter);
        } else {
            viter++;
        }
    }

    auto liter = ilist.begin();
    while (liter != ilist.end()) {
        if (*liter & 1) {
            liter = ilist.erase(liter);
        } else {
            ++liter;
        }
    }
    for (auto i : ivec) {
        cout << i << " ";
    }
    cout << endl;
    for (auto i : ilist) {
        cout << i << " ";
    }
    cout << endl;
}

void pr_9_27()
{
    forward_list<int> flst = {0,1,2,3,4,5,6,7,8,9};
    auto prev = flst.before_begin();
    auto curr = flst.begin();
    while (curr != flst.end()) {
        if (*curr & 1 ) {
           curr = flst.erase_after(prev);
        } else {
            prev = curr;
            ++curr;
        }
    }
    for (auto i : flst) {
        cout << i << " ";
    }
    cout << endl;
}

void pr_9_28(const string &s1, const string &s2, forward_list<string> &sflst)
{
    auto prev = sflst.before_begin();  // 前驱元素
    auto curr = sflst.begin();  // 当前元素
    bool inserted = false;
    while (curr != sflst.end()) {
        if (*curr == s1) {  // 找到给定字符串
            curr = sflst.insert_after(curr, s2);  // 插入新字符串，curr 指向它
            inserted = true;
        }
        prev = curr;  // 前驱迭代器向前推进
        curr++;  // 当前迭代器向前推进
    }
    if (!inserted) {
        sflst.insert_after(prev, s2);  // 未找到给定字符串，插入尾后，注意经过上面的循环
                                       // 此时 prev已经是最后一个元素了
    }
}

void pr_9_31()
{
    list<int> ilist = {0,1,2,3,4,5,6,7,9};
    forward_list<int> flist = {10, 11, 12,13,14,15,16,17,18,19,20};

    auto list_iter = ilist.begin();
    while (list_iter != ilist.end()) {
        if (*list_iter % 2) {
            list_iter = ilist.insert(list_iter, *list_iter);
            list_iter++;
            list_iter++;
        } else {
            list_iter = ilist.erase(list_iter);
        }
    }
    for (auto i : ilist) {
        cout << i << " ";
    }
    cout << endl;
    // 前向链表需要注意前驱、后继的位置
    auto flist_curr = flist.begin();
    auto flist_prev = flist.before_begin();
    while (flist_curr != flist.end()) {
        if (*flist_curr % 2) {
            flist_curr = flist.insert_after(flist_curr, *flist_curr);
            flist_prev = flist_curr;
            flist_curr++;
        } else {
            flist_curr = flist.erase_after(flist_prev);
        }
    }
    for (auto i : flist) {
        cout << i << " ";
    }
    cout << endl;
}

void pr_9_34()
{
    vector<int> vi = {0,1,2,3,4,5,6,7,8,9};;
    auto iter = vi.begin();
    string tmp;
    while (iter != vi.end()) {
        if (*iter % 2) {
            iter = vi.insert(iter, *iter);
        }
        for (auto begin = vi.begin(); begin != vi.end(); ++begin) {
            cout << *begin << " ";
        }
        cout << endl;
        cin >> tmp;
    }
    ++iter;
}

void pr_9_41()
{
    vector<char> vs = {'h','e','l','l','o'};
    string s1(vs.data(), vs.size());
    cout << s1 << endl;
}

void pr_9_42()
{
    string s;
    s.reserve(100);
    char c;
    while (cin >> c) {
        s.push_back(c);
    }
    cout << s << endl;
}

void pr_9_43(string &s, const string &oldVal, const string &newVal)
{
    auto l = oldVal.size();
    if (!l) {
        return;  // 要查找的字符串为空
    }

    auto iter = s.begin();
    while (iter <= s.end() - 1) {  // 末尾少于 oldVal长度的部分无须检查
        auto iter1 = iter;
        auto iter2 = oldVal.begin();
        // s中iter开始的字串必须每个字符都与 oldVal相同
        while (iter2 != oldVal.end() && *iter1 == *iter2) {
            iter1++;
            iter2++;
        }
        if (iter2 == oldVal.end()) {  // oldVal耗尽——字符串相等
            iter = s.erase(iter, iter1);  // 删除s中与oldVal相等部分
            if (newVal.size()) {  // 替换字串是否为空
                iter2 = newVal.end();  // 由后至前逐个插入newVal中的字符
                do {
                    iter2--;
                    iter = s.insert(iter, *iter2);
                } while (iter2 > newVal.begin());
            }
            iter += newVal.size();  // 迭代器移动到新插入内容之后
        } else {
            iter++;
        }
    }
}

void pr_9_44(string &s, const string &oldVal, const string &newVal)
{
    int p = 0;  // 下标索引
    while ((p = s.find(oldVal, p)) != string::npos) {  // 在s中查找 oldVal
        s.replace(p, oldVal.size(), newVal);  // 将找到的字串替换为newVal的内容
        p += newVal.size();  // 下标调整到新插入内容之后
    }
}

void pr_9_45(string &name, const string &prefix, const string &suffix)
{
    name.insert(name.begin(), 1, ' ');
    name.insert(name.begin(), prefix.begin(), prefix.end());
    name.append(" ");
    name.append(suffix.cbegin(), suffix.cend());
}

void pr_9_46(string &name, const string &prefix, const string &suffix)
{
    name.insert(0, " ");
    name.insert(0, prefix);
    name.insert(name.size(), " ");
    name.insert(name.size(), suffix);
}

void pr_9_47()
{
    string s1("ab2c3d7R4E6");
    string numbers("0123456789");
    string letters("abcdefghigklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ");

    string::size_type pos = 0;
    while ((pos = s1.find_first_of(numbers, pos)) != string::npos) {
        cout << "found number at index: " << pos
             << " elements value is: " << s1[pos] << endl;
        pos++;
    }
    pos = 0;
    while ((pos = s1.find_first_of(letters, pos)) != string::npos) {
        cout << "found letter at index: " << pos
             << " elements value is: " << s1[pos] << endl;
        pos++;
    }
    pos = 0;
    while ((pos = s1.find_first_not_of(letters, pos)) != string::npos) {
        cout << "found number at index: " << pos
             << " elements value is: " << s1[pos] << endl;
        pos++;
    }
    pos = 0;
    while ((pos = s1.find_first_not_of(numbers, pos)) != string::npos) {
        cout << "found letter at index: " << pos
             << " elements value is: " << s1[pos] << endl;
        pos++;
    }
}

void pr_9_49(ifstream &in)
{
    string s, longest_word;
    int max_length = 0;
    while (in >> s) {
        if (s.find_first_of("bdfghjklpqty") != string::npos) {
            continue;  // 阿
        }
        cout << s << " ";
        if (max_length < s.size()) {
            max_length = s.size();
            longest_word = s;
        }
    }
    cout << endl << "最长字符串: " << longest_word << endl;
}

void pr_9_50()
{
    vector<string> sVec{"0", "1", "2", "3", "4"};
    int result = 0;
    for (auto &s : sVec) {
        result += stoi(s);
    }
    cout << result << endl;
    vector<string> dVec{"0.1", "1.1", "2.2", "3.3", "4.4"};
    double d = 0.0;
    for (auto &s : dVec) {
        d += stod(s);
    }
    cout << d << endl;
}

// 表示栈中对象的不同类型
enum obj_type {
    LP, RP, ADD, SUB, VAL
};
struct obj {
    obj(obj_type type, double val = 0) { t = type; v = val; }
    obj_type t;
    double v;
};

inline void skipws(string &exp, size_t &p)
{
    p = exp.find_first_of(" ", p);
}

inline void new_val(stack<obj> &so, double v)
{
    if (so.empty() || so.top().t == LP) {
        so.push(obj(VAL, v));
        cout << "push " << v << endl;
    } else if (so.top().t == ADD || so.top().t == SUB) {
        // 之前是运算符
        obj_type type = so.top().t;
        so.pop();
//        if (type == ADD) {
//            cout << "pop +" << endl;
//        } else {
//            cout << "pop -" << endl;
//        }
//        cout << "pop " << so.top().v << endl;
        // 执行加减法
        if (type == ADD) {
            v += so.top().v;
        } else {
            v = so.top().v - v;
        }
        so.pop();
        so.push(obj(VAL, v));  // 运算结果压栈
        cout << "push " << v << endl;
    } else {
        throw invalid_argument("缺少运算符");
    }
}

void pr_9_52()
{
    stack<obj> so;
    string exp;
    size_t p = 0, q;
    double v;
    cout << "请输入表达式：" << endl;
    getline(cin, exp);
    while (p < exp.size()) {
        skipws(exp, p);  // 跳过空格
        if (exp[p] == '(') {
            so.push(obj(LP));
            p++;
            cout << "push LP" << endl;
        } else if (exp[p] == '+' || exp[p] == '-') {
            if (so.empty() || so.top().t != VAL) {
                throw invalid_argument("缺少运算符");
            }
            if (exp[p] == '+') {
                so.push(obj(ADD));
            } else {
                so.push(obj(SUB));
            }
            p++;
            cout << "push " << exp[p - 1] << endl;
        } else if (exp[p] == ')') {
            p++;
            if (so.empty()) {
                throw invalid_argument("未匹配右括号");
            }
            if (so.top().t == LP) {
                throw invalid_argument("空括号");
            }
            if (so.top().t == VAL) {
                v = so.top().v;
                so.pop();
                cout << "pop " << v << endl;
                if (so.empty() || so.top().t != LP) {
                    throw invalid_argument("未匹配右括号");
                }
                so.pop();
                cout << "pop LP" << endl;
                new_val(so, v);
            } else {
                throw invalid_argument("缺少运算数");
            }
        } else {
            v = stod(exp.substr(p), &q);
            p += q;
            new_val(so, v);
        }
    }
    if (so.size() != 1 || so.top().t != VAL) {
        throw invalid_argument("非法表达式");
    }
    cout << so.top().v << endl;
}

int main()
{
    pr_9_50();
    return 0;
}
